#include "exp_4.h"
Boolean less(Node* a, Node* b) { return a->val < b->val; }
Boolean greater(Node* a, Node* b) { return a->val > b->val; }

//交换两个顶点之间的值
void Node_swap(BinTree* tree, int i, int j) {
    ElemType tmp = tree->list.data[i]->val;
    tree->list.data[i]->val = tree->list.data[j]->val;
    tree->list.data[j]->val = tmp;
}
Status head_clear(BinTree* tree){
    int i;
    //0元素也申请了空间
    for(i = 0; i < tree->list.size; ++i){
        if(tree->list.data[i]!=NULL){
            free(tree->list.data[i]);
        }
    }
    SqList_clear(&tree->list);
}

void make_heap(BinTree* tree, ElemType l[], int len,
    Boolean(*cmp)(Node*, Node*)) {
    int i;
    SqList_init_capacity(&tree->list, len);
    tree->list.size = len;
    tree->cmp = cmp;
    //为树申请空间并复制元素
    //头节点可作为临时变量
    tree->list.data[0] = (Node*)malloc(sizeof(Node));
    for (i = 1; i <= len; ++i) {
        //树节点的初始化
        tree->list.data[i] = (Node*)malloc(sizeof(Node));
        tree->list.data[i]->lchild = NULL;
        tree->list.data[i]->rchild = NULL;
        tree->list.data[i]->val = l[i - 1];
    }
    tree->root = tree->list.data[1];
    //连接树的每一个节点
    int mid = len / 2;
    for (i = 1; i <= mid; ++i) {
        tree->list.data[i]->lchild = tree->list.data[i * 2];
        if (i * 2 + 1 <= len) {
            tree->list.data[i]->rchild = tree->list.data[i * 2 + 1];
        }
    }
    //初始化堆
    int j = 0;
    for (i = len / 2; i > 0; i--) {
        tree->list.data[0]->val =
            tree->list.data[i]->val; //把将要比较的结点值放入头结点
        for (j = 2 * i; j <= len; j *= 2) {
            if (j < len &&
                cmp(tree->list.data[j + 1], tree->list.data[j])) {
                j++; // j表示小的那一个孩子的下标
            }
            if (cmp(tree->list.data[0], tree->list.data[j]) || tree->list.data[0]->val == tree->list.data[j]->val)
                break;
            else {
                tree->list.data[i]->val = tree->list.data[j]->val;
                i = j;
            }
        }
        tree->list.data[i]->val = tree->list.data[0]->val;
    }
}

Status top_heap(BinTree* tree, ElemType* e) {
    if (tree->list.size == 0) {
        return ERROR;
    }
    *e = tree->list.data[1]->val;
    return OK;
}

Status pop_heap(BinTree* tree, ElemType* e) {
    if (tree->list.size == 0) {
        return ERROR;
    }
    if (e != NULL) {
        *e = tree->list.data[1]->val;
    }
    //储存末尾元素的值
    tree->list.data[0]->val = tree->list.data[tree->list.size]->val;
    //删除末尾元素
    //如果-1后的size为0，那么末尾元素为根节点
    if (tree->list.size > 1) {
        if (tree->list.size % 2 == 1) {
            //末尾元素为左孩子
            free(tree->list.data[tree->list.size / 2]->rchild);
            tree->list.data[tree->list.size / 2]->rchild = NULL;
        }
        else {
            //末尾元素为右孩子
            free(tree->list.data[tree->list.size / 2]->lchild);
            tree->list.data[tree->list.size / 2]->lchild = NULL;
        }
    }
    else {
        free(tree->list.data[1]);
        tree->list.data[1] = NULL;
        return OK;
    }
    --tree->list.size;
    //从根开始，为最后一个元素寻找位置
    int cur = 1, child = 2;
    while (child <= tree->list.size) {
        //寻找更小或更大的孩子节点
        if (child < tree->list.size && tree->cmp(tree->list.data[child + 1],tree->list.data[child])) {
            ++child;
        }
        //找到位置了
        if (tree->cmp(tree->list.data[0], tree->list.data[child])) {
            break;
        }
        //孩子上浮
        tree->list.data[cur]->val = tree->list.data[child]->val;
        cur = child;
        child *= 2;
    }
    tree->list.data[cur]->val = tree->list.data[0]->val;
    return OK;
}